TIIS (한국인터넷정보학회)
Current Result Document :
| 한글제목(Korean Title) |
Probabilistic Model for Performance Analysis of a Heuristic with Multi-byte Suffix Matching |
| 영문제목(English Title) |
Probabilistic Model for Performance Analysis of a Heuristic with Multi-byte Suffix Matching |
| 저자(Author) |
Yoon-Ho Choi
|
| 원문수록처(Citation) |
VOL 07 NO. 04 PP. 0711 ~ 0725 (2013. 04) |
한글내용
(Korean Abstract) |
|
영문내용
(English Abstract) |
A heuristic with multi-byte suffix matching plays an important role in real pattern matching algorithms. By skipping many characters at a time in the process of comparing a given pattern with the text, the pattern matching algorithm based on a heuristic with multi-byte suffix matching shows a faster average search time than algorithms based on deterministic finite automata. Based on various experimental results and simulations, the previous works show that the pattern matching algorithms with multi-byte suffix matching performs well. However, there have been limited studies on the mathematical model for analyzing the performance in a standard manner. In this paper, we propose a new probabilistic model, which evaluates the performance of a heuristic with multi-byte suffix matching in an average-case search. When the theoretical analysis results and experimental results were compared, the proposed probabilistic model was found to be sufficient for evaluating the performance of a heuristic with suffix matching in the real pattern matching algorithms.
|
| 키워드(Keyword) |
Heuristic matching
suffix matching
probabilistic model
average-case search
pattern matching
|
| 파일첨부 |
PDF 다운로드
|
